/*
 * @lc app=leetcode.cn id=518 lang=golang
 *
 * [518] 零钱兑换 II
 */

// 2. 动态规划
// @lc code=start
func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for i := 0; i < len(coins); i++ {
		for j := coins[i]; j <= amount; j++ {
			dp[j] += dp[j-coins[i]]
		}
	}
	return dp[amount]
}

// @lc code=end

// 1. 深度优先 超时 8/28
// @lc code=start
func change(amount int, coins []int) (ans int) {
	history := []int{}

	var dfs func(money, level int)
	dfs = func(money, level int) {
		if money == amount && !contain(history, level) {
			ans++
			history = append(history, level)
			return
		}
		if money > amount {
			return
		}

		for i := 0; i < len(coins); i++ {
			dfs(money+coins[i], level+1)
		}
	}
	dfs(0, 0)
	return
}

func contain(nums []int, num int) bool {
	for i := 0; i < len(nums); i++ {
		if nums[i] == num {
			return true
		}
	}
	return false
}

// @lc code=end

